All Questions
7 questions
2votes
1answer
296views
Characterization of integral polyhedra
A rational polyhedron $P \subseteq \mathbb{R}^n$ is an integral polyhedron if it is the convex hull of its integer points. That is, if $P = conv(P \cap \mathbb{Z}^n)$. Equivalently, $P$ is integral if ...
- 649
8votes
0answers
382views
What exactly did Lenstra prove on mixed integer linear program?
I studied Lenstra's paper https://www.jstor.org/stable/3689168. I have no clue what complexity he provides on Mixed Integer Programming (it is too terse and it is not a stand alone paper as he assumes ...
- 13.5k
2votes
0answers
81views
General covering approximation
Consider the following integer program (general covering): $\min c \cdot x$ subject to $Ax \ge b$, where all entries in $A, b, c$ are nonnegative and $x$ is required to be nonnegative and integral. ...
- 233
4votes
0answers
1kviews
How to determine proper rounding in linear programming relaxations?
Recall that in the vertex cover problem we are given an undirected graph ${G=(V,E)}$ and we want to find a minimum-size set of vertices ${S}$ that “touches” all the edges of the graph, that is, such ...
- 141
2votes
1answer
2kviews
Solve a simple system of linear inequalities in natural numbers
I want to find a solution to a system of linear inequalities of the following form \begin{aligned} a_1 + b &\ge a_2 \\\ \vdots \\\ a_4 + c &\ge a_1 \end{aligned} where $a_i \in \mathbb N \...
- 37
1vote
2answers
922views
Known sparse integer programming problems
I am studying the properties of sparse integer programming problems, Would like to know if there are any interesting known problems of that type ? I would define sparse problems as problems that have ...
- 113
22votes
3answers
3kviews
How fast can we solve a totally unimodular integer linear program?
(This is a follow-up to this question and its answer.) I have the following totally unimodular (TU) integer linear program (ILP). Here $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$ ...
- 1,404
